import javax.swing.*;
import java.awt.event.*;
import java.awt.*;


import java.io.*;
import java.lang.*;
import java.lang.reflect.Array;
import java.util.*;
import javax.swing.tree.*;

/*
public class DynamicTree{
	
	public static void addChild(Node theParent, int theId){
	    //Node parent = theParent;
	    //int  id 	= theId;
	    int  count;
		Node child = new Node(theParent,theId);
		count 	   = theParent.childCounter++;
		theParent.Children.add(count,child);
		
		}
  
	public static void addUser(Node theParent, String theId){
		
		int count;
		
		//if(theParent.leafNode){
			MobileUser user = new MobileUser(theParent,theId);
			count = theParent.userCounter;
			theParent.Users.add(count,user);
		//}
	}
	/*	
	public static void main (String [] args)throws Exception{
		 
		Node a = new Node();
		addChild(a,2);
		addChild(a,1);
		addChild(a,3);
		
		for(int i = 0; i< a.childCounter;i++)
		{
			System.out.println("the children of node "+a.id+" are "+((Node)a.Children.get(i)).id);
		}
		
	}
	

}
*/
class Node {
   Node parent;
   int id,childCounter = 0, userCounter = 0;
   ArrayList<Node> Children = new ArrayList<Node>();
   ArrayList<MobileUser> Users = new ArrayList<MobileUser>();
   ArrayList<MobileUser> myGlobalUsers;
   ArrayList<AddressRecord>DescendantAddress;
   ArrayList<MU_History>HistoryRecords;
   ArrayList<Replica>Replicas;
   
   Hashtable<Node,MobileUser> lookUp = new Hashtable<Node,MobileUser>();
   
   Node[] myGlobalArray;
   boolean leafNode = false;
   boolean active;
   TransType curTransType;
   JTextArea outpArea;
   Node(Node theParent, int id, Node[] globalArray,JTextArea area, ArrayList<MobileUser> GlobalUsers){
	   this.parent = theParent;
	   this.id	   = id;
	   myGlobalArray = globalArray;
	   active = false;
	   DescendantAddress = new ArrayList<AddressRecord>();
	   curTransType = TransType.ADDRESS;
	   outpArea = area;
	   HistoryRecords = new ArrayList<MU_History>();
	   Replicas = new ArrayList<Replica>();
	   myGlobalUsers = GlobalUsers;
   }
   Node(Node[] globalArray, JTextArea area, ArrayList<MobileUser> GlobalUsers){
	   myGlobalArray = globalArray;
	   this.parent = null;
	   this.id = 0;   	   
	   active = false;
	   DescendantAddress = new ArrayList<AddressRecord>();
	   curTransType = TransType.ADDRESS;
	   outpArea = area;
	   HistoryRecords = new ArrayList<MU_History> ();
	   Replicas = new ArrayList<Replica> ();
	   myGlobalUsers = GlobalUsers;
   }
   
   Node(Node theParent, int theId, boolean theleafNode){
	   this.parent = theParent;
	   this.id	   = theId;
	   
	   if(theleafNode)
		   this.leafNode = true;
	   
   }

  public void addChild(Node Child)
  {
	  this.Children.add(Child);
	  this.addDescCellAddress(Child.getId());
  }
   
  //Adds a descendant to the nodes record of explicit addresses
  //then tells its parent to do the same (unless it is the root)
   public void addDescCellAddress(int descId)
   {
	//Fixing This DescendantAddress.add (new AddressRecord(descId));
   DescendantAddress.add(new AddressRecord(descId));
   //outpArea.append("Record " + id + " " + descId + "\n");
   if(parent != null)
	{
		 parent.addDescCellAddress(descId);
    }
  }
  public int getId()
  {
	  return id;
	  
  }
  public void deactivate ()
  {
	  active = false;
	  
  }
  public void activate ()
  {
	  active = true;
  }
  public boolean getActive()
  {
	  return active;
  }
  //verifies if the given node has a cell with  DescednantId 
  //as a descednant
  public boolean hasDescendant(int DescendantId)
  {
	  for(int i = 0; i < DescendantAddress.size(); i++)
	  {
		  if(DescendantId ==DescendantAddress.get(i).getId())
		  {
		    	  return true;
	      }
		  
	  }
	  return false;
  }
  //returns the index of the Descendant Entry with a given Id
  public int getDescendantIndex(int DescendantId)
  {
	  int index = 0;
	  for(int i = 0; i < DescendantAddress.size(); i++)
	  {
		  if(DescendantId ==DescendantAddress.get(i).getId())
		  {
		    	  index = i;
	      }
		  
	  }
	  return index;
  }
  public void addUser(MobileUser User)
  {
	  Users.add(User);
	  parent.addUsertoParents(User.getId(), this.id);
	  User.currentCell.parent.updateLookUp(User.currentCell, User);
	  this.activate();
	  
  }
  //updates Parents of the node containing a MU
  //UserId is the id of the MU, cellID is the id of the cell
  //containing the user
  public void addUsertoParents(String UserId, int cellId)
  {	
	  //find the proper Explicit Address record and adds
	  //the mobile user to its list
	  for(int i = 0; i < DescendantAddress.size(); i++)
	  {
		
		  if(cellId ==DescendantAddress.get(i).getId())
			  {
			    	  DescendantAddress.get(i).AddMU(UserId);
			    	  
		      }
			  
		
	  }
	  if (this.parent != null)
	  {
		  
		  parent.addUsertoParents(UserId, cellId);
	  }
	  //HistoryRecords.add(new MU_History(UserId));
	  this.activate();
	  //TODO: add functionality to update the pointer records
  }
  //removes the user from the cells userlist and tells its parent
  //to update its records and search for the destination cell
  public void MoveUser(MobileUser movingUser, int DestCellId)
  {
	  Users.remove(movingUser);
	  parent.MoveUserSearchCA(movingUser, DestCellId);
	  this.activate();
  }
  //boolean to determine if a cell with DescendantId is among a node's descendants

  //function for updating a users location upwards through the tree
  //once it finds the least common ancestor it makes a call
  //to begin propagating the update downwards
  public void MoveUserSearchCA(MobileUser movingUser, int DestCellId)
  {
	  this.activate();
	  //removes the old address of the User from the AddressRecordBook
	  for(int i = 0; i < DescendantAddress.size(); i++)
	  {
		    if(DescendantAddress.get(i).MU_here(movingUser.getId()))
		    {
	        DescendantAddress.get(i).removeMU(movingUser.getId()); 
	        outpArea.append("CA:removing" + movingUser.getId() + "from" + this.id + "\n");
		    }
	  }
	  
	
	 //update the DescendantAddress with the new Address of the Mobile User
	  if(this.hasDescendant(DestCellId))
	  {	
		  if(curTransType == TransType.REPLICATION)
		  {
			  boolean hasRecord = false;
			  for(int i = 0; i < HistoryRecords.size(); i++)
			  {
				  if(HistoryRecords.get(i).equals(movingUser.getId()))
				  {
					  hasRecord = true;
					  HistoryRecords.get(i).setMoves(movingUser.getMoveCounter());
				  }
				  
			  }
			  if(hasRecord == false)
			  {
				  HistoryRecords.add(new MU_History(movingUser.getId()));
				  HistoryRecords.get(HistoryRecords.size() - 1).setMoves(movingUser.getMoveCounter());
				  
			  }
		  }
		    //add the proper entry for MU in the array of Addresses
	    	int index = this.getDescendantIndex(DestCellId);
	    	
	    	DescendantAddress.get(index).AddMU(movingUser.getId());
	    	
	    	//find the child which has the destination Cell as a descendant and tells it to update
	    	for(int i = 0; i < Children.size(); i++)
	    	{
	    		outpArea.append("" + i + "\n");
	    		if (Children.get(i).hasDescendant(DestCellId) || Children.get(i).getId()==DestCellId)
	    		{
	    			Children.get(i).MoveUserDown(movingUser, DestCellId);
	    		}
	    		
	    	}
	    	if(parent != null)
	    	{
	    		parent.MoveUserUp(movingUser, DestCellId);
	    	}
	  }
	 else if(parent != null)//Continue Searching for the least common Ancestor
	 parent.MoveUserSearchCA(movingUser, DestCellId);
	
  }
  
 //found the common ancestor, propogate updates upwards through the tree without
 //searching for the CA (note, pointer implementation has nothing to do here
 public void MoveUserUp(MobileUser movingUser,int destCellId)
 {
	 if(curTransType== TransType.ADDRESS || curTransType == TransType.REPLICATION)
	 {
		  this.activate();
	 }
	  //removes the old address of the User from the AddressRecordBook
	  for(int i = 0; i < DescendantAddress.size(); i++)
	  {
		  if(DescendantAddress.get(i).MU_here(movingUser.getId()))
		    {
	        DescendantAddress.get(i).removeMU(movingUser.getId()); 
	     
		    }
	  }
	  //add user to the correct Address
	  for(int i = 0; i < DescendantAddress.size(); i++)
	  {
		    if(DescendantAddress.get(i).getId() == destCellId)
		    {
		    	DescendantAddress.get(i).AddMU(movingUser.getId());
		    }
	  }
	  if (parent != null)
	  parent.MoveUserUp(movingUser, destCellId);
	 
	  //TODO No need to update pointers beyond the Common Ancestor when Moving
 }
 //found the common Ancestor, propogate updates downward until you reach the Destination Cell
 public void MoveUserDown(MobileUser movingUser, int destCellId)
 {
	 this.activate();
	 //if this is the destination Cell, add  movingUser it to the list of Users
	 //tells user to update its location
	 if(this.id == destCellId)
	 {
		 Users.add(movingUser);
		 movingUser.setLocation(this);
	 }
	 //otherwise update the Descendant lists and continue to search for Destination Cell
	 else
	 {
		 if(curTransType == TransType.REPLICATION)
		  {
			  boolean hasRecord = false;
			  for(int i = 0; i < HistoryRecords.size(); i++)
			  {
				  if(HistoryRecords.get(i).equals(movingUser.getId()))
				  {
					  hasRecord = true;
					  HistoryRecords.get(i).setMoves(movingUser.getMoveCounter());
				  }
				  
			  }
			  if(hasRecord == false)
			  {
				  HistoryRecords.add(new MU_History(movingUser.getId()));
				  HistoryRecords.get(HistoryRecords.size() - 1).setMoves(movingUser.getMoveCounter());
				  
			  }
		  }
		//add user to the correct Address of Descendants
		int index = this.getDescendantIndex(destCellId);
		DescendantAddress.get(index).AddMU(movingUser.getId());
		//find which child has the destination cell as a descendant and tell it to propogate the update
		for(int i = 0; i < Children.size(); i++)
		{
			if(Children.get(i).hasDescendant(destCellId)||Children.get(i).getId() == destCellId)
			{
				Children.get(i).MoveUserDown(movingUser, destCellId);
			
		    }
	    }
		  
	 }
	
	 
	 //TODO: Update pointer lists for Destination Cell
  }
 
 public void callSearchCA(String DestinationId)	 
 {
	 this.activate();
	//Search the list of descendant address records to see if one of the descendants
	 //is hosting a MU with DestinationId
	 for(int i = 0; i < DescendantAddress.size(); i++)
	 {
		 if(DescendantAddress.get(i).MU_here(DestinationId) == true)
		 {
			 if(curTransType == TransType.ADDRESS)
			 {
				 outpArea.append("Found common ancestor at " + this.id + "\n");
			 }
			 this.myGlobalArray[DescendantAddress.get(i).getId()].CallUser(DestinationId);
			 return;
		 }
	 
	 }
	 //otherwise keep Searching for the Common Ancestor
	 parent.callSearchCA(DestinationId);
 }

 //method for following pointers down to cell containing the MU with an id of DestinationId
 public int callReplica(String DestinationId)
 {
	 this.activate();
	 for(int i = 0; i < Replicas.size(); i ++)
	 {
		 if (Replicas.get(i).getName().equals(DestinationId))
		 {
			 int destAddress = Replicas.get(i).getAddress();
			 myGlobalArray[destAddress].CallUser(DestinationId);
			 return 0;
			 
		 }
		 
	 }
	 for(int i = 0; i < DescendantAddress.size(); i++)
	 {
		 if(DescendantAddress.get(i).MU_here(DestinationId) == true)
		 {
			 this.myGlobalArray[DescendantAddress.get(i).getId()].CallUser(DestinationId);
			 return 1;
		 }
	 
	 }
	 int numMoves= 1;
	 int costUpdate = 1;
	 int calls = 1;
	 int savings;
	 for(int i = 0; i < myGlobalUsers.size();i++)
	 {
		if(myGlobalUsers.get(i).getId().equals(DestinationId))
		{
			numMoves= myGlobalUsers.get(i).getMoveCounter();
			costUpdate = myGlobalUsers.get(i).getReplicaCost();
		}
	 }
	 boolean inRecord= false;
	 for(int i = 0; i < HistoryRecords.size(); i++)
	 {
		 if(HistoryRecords.get(i).getId().equals(DestinationId))
		 {
			 inRecord = true;
			 HistoryRecords.get(i).incCalls();
			 calls = HistoryRecords.get(i).getCalls();
			 
		 }
		 
	 }
	 if(!inRecord)
	 {
		 HistoryRecords.add(new MU_History(DestinationId));
	 
	 }
	 savings = 1 + parent.callReplica(DestinationId);
	 this.outpArea.append("Cell ID: " + this.id);
	 this.outpArea.append(" numMoves =" + numMoves);
	 this.outpArea.append(" costUpdate =" + costUpdate);
	 this.outpArea.append(" calls = " + numMoves);
	 this.outpArea.append(" savings = " + savings + "\n");
	 if(savings*calls>= numMoves*costUpdate)
	 {
		 this.outpArea.append("Adding Replica of: " + DestinationId + "\n");
		 addReplica(DestinationId);
	 }
	
	
 return 0;
 }
 public void addReplica(String ReplicaId)
 {
	 int replicaLocation = 0;
	 for(int i = 0; i < myGlobalUsers.size(); i++)
	 {
		 if(myGlobalUsers.get(i).getId().equals(ReplicaId))
		 {
			 replicaLocation = myGlobalUsers.get(i).getLocation().getId();
			 myGlobalUsers.get(i).addReplicaHolder(this);
		 }
	 }
	 Replicas.add(new Replica(ReplicaId, replicaLocation));
	 
 }
 public void updateReplica(String ReplicaId, int newLocation)
 {
	if(curTransType == TransType.REPLICATION)
	{
		this.activate();
	}
	for(int i = 0; i < Replicas.size(); i++)
	{
	 if (Replicas.get(i).getName().equals(ReplicaId))
	 {
		Replicas.get(i).updateReplica(newLocation);
	 }
	}
 }
 /*
 public int getMoves(String MUId)
 {
	for(int i = 0; i < Users.size(); i++) 
	{
		if(Users.get(i).getId().equals(MUId))
			return Users.get(i).getMoveCounter();
	}
	for(int i = 0; i < DescendantAddress.size(); i++)
	{
	 if(DescendantAddress.get(i).MU_here(MUId) == true)
	 {
		 return myGlobalArray[DescendantAddress.get(i).getId()].getMoves(MUId);
		
	 }
	}
	return parent.getMoves(MUId);
 }
 */
 public void callDown(String DestinationId)
 {
	 //TODO: find the pointer to the next cell in your search for Destination MU and follow it

 }
 public void CallUser(String DestinationId)
 {
	this.activate();
	for(int i = 0; i < Users.size(); i++)
	{
		if(Users.get(i).getId().equals(DestinationId))
		{
			//found the right cell
			//Users.get(i).recieveCall();
		}
	}
	
 
 }
 public void setTransType(TransType T)
 {
	 this.curTransType = T;
	 
 }

 // method to update the lookup table at each node when a new mobile user is created
 public void updateLookUp(Node theKey, MobileUser theValue){
		if(curTransType == TransType.POINTER || curTransType == TransType.REPLICATION)
		{
			this.activate();
		}
		if(theKey.parent == null)
		{
			System.out.println("Lookup table Updated");
			theKey.lookUp.put(theKey, theValue);
		}
		else {
			theKey.lookUp.put(theKey, theValue);
			theKey.parent.updateLookUp(theKey.parent,theValue);
		}
	}
 
 
 // delete an entry form the lookup table if the mobile user relocates
 public void removeLookUpEntry(Node theKey,MobileUser theValue)
 {
	 if(curTransType == TransType.POINTER || curTransType == TransType.REPLICATION)
		{
			this.activate();
		}
	
	 theKey.lookUp.remove(theValue);
	 if(theKey.parent != null)
		{
		 theKey.parent.removeLookUpEntry(theKey.parent, theValue);
		}
	 
 }
 
 
 // method to update lookup table when a mobile user is relocated
public void updateLookUp(Node currentCell, Node destCell, MobileUser theValue)
{
	if(curTransType == TransType.POINTER || curTransType == TransType.REPLICATION)
	{
		this.activate();
	}
	currentCell.removeLookUpEntry(currentCell,theValue);
	destCell.updateLookUp(destCell,theValue);
}

//search for a mobile user
public boolean searchUser(Node currentCell,MobileUser theValue)
{
	if(currentCell.lookUp.contains(theValue))
	{
		System.out.println("the mobile user - "+theValue.id+"is located at "+currentCell.id);
		return true;
	}
	return false;
}

 public void callUserPointer(MobileUser destinationUser)
 {
	if(curTransType == TransType.POINTER || curTransType == TransType.REPLICATION)
	{
		this.activate();
	}
	 searchUser(this, destinationUser);
	 if(!searchUser(this, destinationUser))
	 {
		 parent.callUserPointer(destinationUser);
	 }
	 
 }

 //class for maintaining an explicit address record
 //consists of an Id for the id of the cell in the record
 //and a list of Strings corresponding to the IDs of
 //Mobile Users in the cells
class AddressRecord {
	int nodeID;
	ArrayList<String> MobileUsers;
	
	AddressRecord(int Id)
	{
		nodeID = Id;
		MobileUsers = new ArrayList<String>();
		
	}
	public void AddMU(String MUId)
	{
		MobileUsers.add(MUId);
	}
	public void removeMU(String MUId)
	{
		for(int i = 0; i < MobileUsers.size(); i++)
		{
			if(MobileUsers.get(i).equals(MUId))
				MobileUsers.remove(i);
			
		}
		
		
	}
	//determines if there is a record of the mobile user at this descendant address
	public boolean MU_here(String Id)
	{
		for(int i = 0; i < MobileUsers.size(); i++)
		{
			if(Id.equals(MobileUsers.get(i)))
			{
				return true;
			}
		}
		return false;
	}
	public void addReplica()
	{
		
		
	}
	public int getId()
	{
		return nodeID;
	}
	//testing
	

    }

	
}
class MU_History
{
	String MUName;
	int calls;
	int moves;
	
	MU_History(String MU_id)
	{
		MUName = MU_id;
		calls = 0;
		moves = 0;
	}

	String getId()
	{
		return MUName;
		
	}
	void setMoves(int newMoves)
	{
		moves = newMoves;
		
	}
	int getMoves()
	{
		return moves;
		
	}
	int getCalls()
	{
		return calls;
	}
	
	void incCalls()
	{
		calls++;
	}
	
	
}
class Replica
{
	String MUName;
	int MUAddress;

	Replica(String newName, int newAddress)
	{
		MUName = newName;
		MUAddress = newAddress;
		
	
	}
	String getName()
	{
		return MUName;
		
	}
	int getAddress()
	{
		return MUAddress;
		
	}
	void updateReplica(int newAddress)
	{
		MUAddress = newAddress;
	
	}
}